class Solution {
    public int minMutation(String startGene, String endGene, String[] bank) {
        Set<String> hash=new HashSet<>();
        for(String x:bank) hash.add(x);
        if(startGene.equals(endGene)) return 0;
        if(!hash.contains(endGene)) return -1;
        Set<String> vis=new HashSet<>();
        char[] change={'A','C','G','T'};
        Queue<String> q=new LinkedList<>();
        q.add(startGene);
        vis.add(startGene);
        int step=0;
        while(!q.isEmpty()){
            int l=q.size();
            step++;
            while(l-->0){
                String t=q.poll();
                for(int i=0;i<8;i++){
                    char[] tmp=t.toCharArray();
                    for(int j=0;j<4;j++){
                        tmp[i] = change[j];
                        String next=new String(tmp);
                        if(hash.contains(next)&&!vis.contains(next)){
                            if(next.equals(endGene)) return step;
                            q.add(next);
                            vis.add(next);
                        }
                    }
                }
            }
        }
        return -1;
    }
}